package main

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func buildTree(inorder []int, postorder []int) *TreeNode {
	if len(inorder) == 0 {
		return nil
	}
	if len(inorder) == 1 {
		return &TreeNode{
			Val: inorder[0],
		}
	}
	root := postorder[len(postorder)-1]
	pivot := -1
	for i, v := range inorder {
		if v == root {
			pivot = i
			break
		}
	}
	if pivot < 0 {
		return nil
	}
	leftNodes := make(map[int]struct{})
	for _, v := range inorder[:pivot] {
		leftNodes[v] = struct{}{}
	}
	rightNodes := make(map[int]struct{})
	for _, v := range inorder[pivot+1:] {
		rightNodes[v] = struct{}{}
	}
	var leftPost, rightPost []int
	for _, v := range postorder {
		if _, ok := leftNodes[v]; ok {
			leftPost = append(leftPost, v)
		} else if _, ok := rightNodes[v]; ok {
			rightPost = append(rightPost, v)
		}
	}
	return &TreeNode{
		Val:   root,
		Left:  buildTree(inorder[:pivot], leftPost),
		Right: buildTree(inorder[pivot+1:], rightPost),
	}
}

func main() {
	root := buildTree([]int{9, 3, 15, 20, 7}, []int{9, 15, 7, 20, 3})
	println(root)
}
